package com.dhu.graph.digraph;

import com.dhu.graph.basic.GraphImpls.DiGraph;

import java.util.Stack;

/**
 * @ Author ：snow
 * @ Date   ：Created in 2020-05-06
 * @ Description：找出一幅有向图中的强连通分量
 * @ Modified By：
 * @ Version:
 */
public class KosarajuSCC {
    private boolean[] marked;
    private int[] id;       // 强连通分量的id
    private int count;      // 强连通分量的数量

    /**
     * 利用G的反向图中顶点的逆后序来dfs G
     * @param G
     */
    public KosarajuSCC(DiGraph G){
        this.marked = new boolean[G.V()];
        this.id = new int[G.V()];
        DepthFirstSort depthFirstSort = new DepthFirstSort(G.reserve());
        Stack<Integer> sortStack = depthFirstSort.reversePost();
        while(!sortStack.isEmpty()){
            Integer v = sortStack.pop();
            if (!marked[v]){
                dfs(G,v);
                count ++;
            }
        }
    }
    private void dfs(DiGraph G, int s){
        marked[s] = true;
        id[s] = count;
        for (Integer w : G.adj(s)) {
            if (!marked[w])
                dfs (G, w);
        }
    }

    /**
     * 顶点w 和v是否是强连通
     * @param v
     * @param w
     * @return
     */
    public boolean isStronglyConnect(int v, int w){
        return id[w] == id[w];
    }
    public int id(int v){
        return id[v];
    }
    public int count(){
        return this.count;
    }
}
